4.1.9.2 计数排序（稳定排序）
平均时间复杂度 {\displaystyle O(n+k)} O(n+k)
最坏空间复杂度 {\displaystyle O(n+k)} O(n+k)
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i项;
Array.prototype.countSort = function() {
const C = []
// 先算出每个数字出现的次数
for(let i = 0; i < this.length; i++) {
const j = this[i]
C[j] >= 1 ? C[j] ++ : (C[j] = 1)
}
const D = []
for(let j = 0; j < C.length; j++) {
if(C[j]) {
while(C[j] > 0) {
D.push(j)
C[j]--
}
}
}
return D
}
const arr = [11, 9, 6, 8, 1, 3, 5, 1, 1, 0, 100]
console.log(arr.countSort())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21